package 其他.接雨水42;

public class Solution {
    /**
     * 计算给定高度图下雨后能接多少雨水
     *
     * @param height 一系列非负整数表示的高度图
     * @return 返回能接的雨水总量
     */
    public int trap(int[] height) {
        // 数组长度
        int n = height.length;

        // preMax数组用于存储从左向右遍历时，到当前位置为止的最大高度
        int[] preMax = new int[n];
        preMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            preMax[i] = Math.max(preMax[i - 1], height[i]);
        }

        // sufMax数组用于存储从右向左遍历时，到当前位置为止的最大高度
        int[] sufMax = new int[n];
        sufMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            sufMax[i] = Math.max(sufMax[i + 1], height[i]);
        }

        // ans用于累计所有位置能接的雨水总量
        int ans = 0;
        for (int i = 0; i < n; i++) {
            // 每个位置能接的雨水量为其左右最大高度的较小值减去当前位置的高度
            ans += Math.min(preMax[i], sufMax[i]) - height[i];
        }

        // 返回能接的雨水总量
        return ans;
    }

    //方法二

    /**
     * 计算给定高度数组所能捕获的雨水总量
     * 该方法使用双指针技术，从数组的两端开始向中间遍历，同时记录到目前为止遇到的最大高度
     * 这样可以在一次遍历中计算出总的储水量
     *
     * @param height 代表每个位置的高度的整数数组
     * @return 返回捕获的雨水总量
     */
    public int trap2(int[] height) {
        // 数组长度
        int n = height.length;
        // 左右指针初始位置
        int left = 0, right = n - 1;
        // 到目前为止左右 sides 的最大高度
        int leftMax = 0, rightMax = 0;
        // 总的储水量
        int ans = 0;

        // 当左指针不超过右指针时，继续遍历
        while (left <= right) {
            // 更新左侧的最大高度
            leftMax = Math.max(leftMax, height[left]);
            // 更新右侧的最大高度
            rightMax = Math.max(rightMax, height[right]);

            // 比较左右两侧的最大高度，如果左侧最大高度小于右侧最大高度，则说明当前位置的储水量为其左侧最大高度减去当前位置的高度
            if (leftMax < rightMax) {
                // 累加左侧的储水量
                ans += leftMax - height[left];
                // 左指针向右移动
                left++;
            } else { // 如果左侧最大高度大于等于右侧最大高度，则说明当前位置的储水量为其右侧最大高度减去当前位置的高度
                // 累加右侧的储水量
                ans += rightMax - height[right];
                // 右指针向左移动
                right--;
            }
        }
        // 返回总的储水量
        return ans;
    }

}
